/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 17, 2014
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a linked list, return the node where the cycle begins. If
 *              there is no cycle, return null.
 * 
 *              Follow up: Can you solve it without using extra space?
 * 
 *              Length of the cycle: y
 * 
 *              Let hare run two steps while tortoise runs one step
 * 
 *              while both of them entered the cycle, the hare is definetly to
 *              overlap the tortoise at some node, we define it as m:
 * 
 *              The hare totally runs: x + ky + m The tortoise totally runs: x +
 *              ty + m Thus, ky = 2ty + x + m we have (x + m) mod y = 0 We can
 *              conclude that if the hare run more x steps, it will reach the
 *              cycle's starting node.
 */
public class LinkedListCycleII {

	@Test
	public void test() {
		ListNode l1 = new ListNode(1);
		ListNode l2 = new ListNode(2);
		ListNode l3 = new ListNode(3);
		ListNode l4 = new ListNode(4);
		ListNode l5 = new ListNode(5);
		ListNode l6 = new ListNode(6);
		ListNode l7 = new ListNode(7);

		l1.next = l2;
		l2.next = l3;
		l3.next = l4;
		l4.next = l5;
		l5.next = l6;
		l6.next = l7;
		l7.next = l2;

		System.out.println(detectCycle(l1).val);
	}

	private class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	public ListNode detectCycle(ListNode head) {
		if (head == null)
			return head;
		ListNode slow = head;
		ListNode fast = head;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			if (slow == fast)
				break;
		}
		if (fast == null || fast.next == null)
			return null;
		slow = head;
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return fast;
	}

}
